package cn.bouncyslime.huffmanTree.util;

import cn.bouncyslime.huffmanTree.entity.Node;

import java.util.*;

/**
 * 作者： 张一卓
 * 时间： 2019/12/31 11:16
 */
public class HuffmanTree {
    /**
     * 用来存放赫夫曼编码的map
     */
    private Map<Character, String> map = new HashMap<>();

    /**
     * 根据存放有Node的List构造赫夫曼树，并返回赫夫曼树的根结点
     *
     * @param list 存放有所有用于构造赫夫曼树的Node的列表
     * @return 返回所构造的赫夫曼树的根结点
     */
    public Node createTree(List<Node> list) {
        // 当list列表中只剩下的一个Node时，这个Node就是根节点，之后停止遍历，返回根结点
        while (list.size() > 1) {
            // 对node列表进行排列，因为重写了Node的compareTo方法，所以此排序会将weight更小的排序到列表末端
            Collections.sort(list);
            Node left = list.get(list.size() - 1);
            Node right = list.get(list.size() - 2);
            // 只有叶子节点才是存放有真正字符的节点，叶子结点的父节点的权重是为了进一步确定其在树中的位置
            Node parent = new Node(null, left.getWeight() + right.getWeight());
            parent.setLeftNode(left);
            parent.setRightNode(right);
            list.remove(left);
            list.remove(right);
            list.add(parent);
        }
        Node root = list.get(0);
        // 生成赫夫曼树之后生成赫夫曼编码
        getHuffmanCode(root);
        // 对赫夫曼树进行中全为0的编码进行处理
        preventAllZeroString(root);
        return root;
    }

    /**
     * 根据字符统计的map来得出所有用来构造赫夫曼树的node，并将它们添加到一个List中
     *
     * @param map 字符统计map
     * @return 包括所有节点的Node列表
     */
    public static List<Node> getAllHuffmanNode(Map<Character, Integer> map) {
        List<Node> list = new LinkedList<>();
        // 将map中收集到的数据放到 Node节点 的列表中
        map.forEach((k, v) -> list.add(new Node(k, v)));
        return list;
    }

    /**
     * 递归生成赫夫曼编码，并将哈弗曼编码保存到一个Map中
     * <p>
     * 赫夫曼树已经构造完毕，其是一个排序二叉树，则其左节点的权重肯定比父节点的小，右节点的权重肯定比父节点的大
     * 则递归遍历过程中，在左节点的code末尾加0，在右节点的末尾加1
     *
     * @param root 赫夫曼树的根结点
     */
    private void getHuffmanCode(Node root) {
        // 递归的边界条件
        if (root == null) {
            return;
        }
        // 因为赫夫曼树已经
        if (root.getLeftNode() != null) {
            root.getLeftNode().setCode(root.getCode() + "0");
            // 当data不为空时，说明其实叶子结点，则将其添加到用来存放字符和其赫夫曼编码的map当中
            if (root.getLeftNode().getData() != null) {
                map.put(root.getLeftNode().getData(), root.getLeftNode().getCode());
            }
        }
        if (root.getRightNode() != null) {
            root.getRightNode().setCode(root.getCode() + "1");
            // 当data不为空时，说明其实叶子结点，则将其添加到用来存放字符和其赫夫曼编码的map当中
            if (root.getRightNode().getData() != null) {
                map.put(root.getRightNode().getData(), root.getRightNode().getCode());
            }
        }
        getHuffmanCode(root.getLeftNode());
        getHuffmanCode(root.getRightNode());
    }

    /**
     * 为了防止构造出来的赫夫曼编码中出现某一个编码规则全为0时
     * 导致的在解码时将编码结果最后的没有任何意义的多个0解析为相应字符的情况
     *
     * @param root 赫夫曼树的根结点
     */
    private void preventAllZeroString(Node root) {
        while (root.getLeftNode() != null) {
            root = root.getLeftNode();
        }
        root.setRightNode(new Node(root.getData(), root.getWeight()));
        root.getRightNode().setCode(root.getCode() + "1");
        map.put(root.getData(), root.getRightNode().getCode());
        root.setData((char) 0);
    }

    /**
     * getter方法，用来获取私有变量：存放赫夫曼编码的map
     *
     * @return Map
     */
    public Map<Character, String> getCodeMap() {
        return map;
    }
}
